This invention relates generally to a reduction in the computational effort of decoding error control codes, and more particularly to an improved method of breadth-first decoding of convolutional codes.
In digital communication systems, it is commonplace to use error control codes to maintain reliable data reception. Error control coding adds redundancy to a sequence of symbols, and at the receiver this redundancy is used to correct errors in the noisy received sequences.
Error control codes have traditionally been divided into two categories, namely block codes and convolutional codes. In a block code, k information symbols are encoded into a larger block of n code symbols, to produce a rate k/n code. In a convolutional code, an ongoing stream of information symbols is continuously encoded, with a code rate of k/n being produced by repeatedly shifting k information symbols into a shift register, and for each set of k information symbols the encoder produces n code symbols based on the information symbols in the shift register and the encoder structure.
Regardless of whether the coding is block or convolutional, the vast majority of the computational effort occurs at the decoder, whose task is to estimate which coded symbol sequence best corresponds to the received noisy sequence of symbols. A well known decoder is the Viterbi algorithm (VA), which produces a maximum-likelihood sequence estimate and is thus optimal (in the sense of minimizing the probability of sequence error, given equally likely occurring information sequences). The VA was first used in the context of convolutional codes, then for intersymbol interference sequence estimation, and more recently in the context of decoding block codes. For background information on the VA and its applications the reader is referred to G. D. Forney Jr., "The Viterbi algorithm," Proc. IEEE, vol. 61, pp. 268-278, 1973., and J. K. Wolf, "Efficient maximum likelihood decoding of linear block codes using a trellis," IEEE Trans. Inform. Theory, vol. IT-24, pp. 76-80, January 1978. Use of the Viterbi Algorithm and its derivatives is not limited, however, to digital communications; it can be used in other probabilistic decision-making or pattern-matching processes, for example, speech or character recognition or decoding in computer peripheral storage devices.
Unfortunately, the computational complexity of the VA can be one of the most significant computational loads in a receiver. The VA's computational effort arises from the fact that it performs a search of all the paths through a potentially large trellis diagram. In this trellis, the branches represent the allowable sequences in the code, and the nodes represent the possible encoder states (e.g. shift register contents, in the case of a convolutional code). The width of the trellis (in terms of the number of possible encoder states) depends exponentially on the memory of the code (e.g. the shift-register length, in the case of a convolutional code). A large computational load is disadvantageous for many applications, such as digital cellular telephones which rely on battery power, and for applications that require very high speed decoding.
Consequently, efforts have been made towards obtaining improved trade-offs between coding performance and complexity. Some of these efforts have gone towards improving the efficiency of implementing maximum-likelihood decoders such as the VA, while other approaches use sub-optimal (non-maximum-likelihood) decoders to hopefully obtain greater reductions in complexity. Various sub-optimal decoding schemes are summarized in the literature; for example, see J. B. Anderson and S. Mohan, "Sequential decoding algorithms: A survey and cost analysis," IEEE Trans. Commun., vol. COM-32, pp. 169-176, February 1984. These approaches include the stack algorithm, the Fano algorithm (see R. M. Fano, "A heuristic discussion of probabilistic decoding," IEEE Trans. Inform. Theory, pp. 64-74, April 1963; and U.S. Pat. No. 3,457,562), and breadth-first decoding schemes such as the M-algorithm.
By breadth-first, we mean that the decoding search extends paths through a code tree (or trellis, which is a more compact representation of the code tree) where all of the paths in storage are of the same length. The VA is a breadth-first search, and it searches the entire trellis. The M algorithm is also a breadth-first search, but in the M algorithm only the best M paths are retained at each depth in the tree (or trellis). Breadth-first partial searches of a code tree have are particularly attractive in that they are inherently parallel, which facilitates implementation in parallel hardware. For more details on the M algorithm, the reader is referred to J. B. Anderson and S. Mohan, Coding: An Algorithmic Approach, Kluwer, 1990, and S. Mohan and A. K. Sood, "A multiprocessor architecture for the (M,L)-algorithm suitable for VLSI implementation," IEEE Trans. Commun., vol COM-34, pp. 1218-1224, December 1986.
The most significant computational bottleneck in M algorithm decoding of error control codes has been the task of finding the best M metrics at each depth in the tree (or trellis). We refer to this task as metric sifting. In A. D. Kot, "A linear-time method for contender sifting in breadth-first decoding of error control codes," 1993 Canadian Conference on Electrical and Computer Engineering, Vancouver Canada, September 1993, (Kot 93) a method is described that can provide a sorted set of metrics during M algorithm decoding of binary linear block codes using only M comparisons. This is a significant improvement over comparison-based sorting, which requires O(Mlog.sub.2 M) comparisons. This is also a significant improvement over Hadian and Sobel's comparison-based selection method (see D. E. Knuth, The Art of Computer Programming: Volume III, Sorting and Searching, Addison Wesley, 1973) where the best metrics are found without regard to order. An example of a non-comparison-based method is reported in S. J. Simmons, "A nonsorting VLSI structure for implementing the (M,L) algorithm," IEEE J. Selected Areas Commun., Vol. JSAC-6, pp. 538-546, April 1988., which cannot be directly and fairly compared since the types of operations are dissimilar.
The efficiency of the metric sifting method reported in Kot93 arises from exploiting an ordering that is inherent in the metrics. The method for binary linear block codes can be briefly summarized as follows. Imagine that there are M paths (survivors) in a code tree search whose metrics are extended to form 2M metrics. The task is to sift out the best M metrics from among these 2M metrics. Assume that the M metrics prior to extension were available in sorted order. The method proceeds by organizing the 2M extended metrics into two subsets, where one subset corresponds to extension by a 0 bit, and the other corresponds to extension by a 1 bit. It is shown in Kot93 (in particular, FIG. 3) that this organization preserves metric order within each subset. The already ordered subsets are then merged (which is much more efficient than sorting) to provide a sorted set of M survivor metrics.
The metric sifting method of Kot93 is also applicable to decoding convolutional codes. In the application of merge sifting to convolutional codes, the method described in Kot93 for merging two subsets and repeating for each of the n bits in a branch, will be referred to as Bit-by-Bit Merge Sifting. It is applicable to both binary block codes and convolutional codes but is about one-third as computationally efficient for rate 1/2 convolutional codes as for block codes.
Accordingly, a need remains to further improve the efficiency of breadth-first decoding of convolutional codes.